1. Field of the Invention
The present invention firstly relates to a process for storing, in a first communication apparatus, data-link-layer path information indicating a communication path in a data link layer (layer 2) from the first communication apparatus to one of at least one second communication apparatus, where the first and at least one second communication apparatuses are each connected to a network which is logically divided into a plurality of subnetworks based on network-layer addresses. The present invention also relates to a product which, when used with a communication apparatus, is able to output control information which directs the communication apparatus to execute the above process. The present invention further relates to a communication apparatus generated by the above process.
The present invention secondly relates to a process for searching, at a first communication apparatus, for one of at least one piece of data-link-layer (layer-2) or network-layer (layer-3) path information indicating a communication path in a data link layer or in a network layer from the first communication apparatus to one of at least one second communication apparatus, based on a network-layer (layer-2) address of the one of the at least one second communication apparatus, where the first communication apparatus and the at least one second communication apparatuses are each connected to a network as above. The present invention also relates to a product which, when used with a communication apparatus, is able to output control information which directs the communication apparatus to execute the above process.
The present invention thirdly relates to a process and an apparatus for determining layer-2 (data-link-layer) reachability between first and second communication apparatuses, where each of the first and second communication apparatuses are connected to a layer-3 (network-layer) communication network comprised of at least one router and a plurality of subnetworks which are logically defined over at least one layer-2-connected communication network. The present invention also relates to a product which, when used with a communication apparatus, is able to output control information which directs the communication apparatus to execute the functions of the above apparatus for determining layer-2 reachability.
The present invention fourthly relates to an apparatus, for use with each of at least one router provided in a layer-3 communication network comprised of a plurality of subnetworks which are logically defined over at least one layer-2-connected communication network, and for determining layer-2 reachability between first and second communication apparatuses each connected to the layer-3 communication network, where a layer-3 communication path passing a portion or all of the at least one router can be determined by the portion or all of the at least one router based on a layer-3 address of the second communication apparatus. The present invention also relates to a product which, when used with a communication apparatus, is able to output control information which directs the communication apparatus to execute the functions of the above apparatus for use with each router in determining layer-2 reachability.
2. Description of the Related Art
2.1 LANs (local area networks) are constructed in respective sections or task groups in many companies and campuses, and those LANs are interconnected through relaying apparatuses called routers to form a company network or a campus network. Each LAN in such a network is an example of a subnetwork. Namely, a plurality of subnetworks are interconnected to a plurality of routers to form a network.
Each terminal connected to one of the above subnetworks can communicate with another terminal connected to the same subnetwork by directly sending a packet, while each terminal sends a packet to one of the plurality of routers which is located at a boundary of the subnetwork to which the terminal is connected, when the said each terminal communicates to another terminal which is connected to a different subnetwork. When the router receives the packet, the router determines to which router the packet is to be transferred, and then transfers the packet to the determined router. Thus, communication to a terminal connected to a different subnetwork is possible.
In a typical terminal, transmission processing of a packet is performed by an operating system (OS). The packet is transmitted based on a network-layer address, For example, according to the Internet protocol (IP), an IP address is used in transmission. The transmission processing of a packet according to the Internet protocol (IP) is explained below.
The operating system (OS) has a routing table corresponding to all the network-layer addresses which are reachable from the host (router) which contains the operating system, and each entry of the routing table contains a network address, an output interface of the host, a gateway address, and the like. The gateway address is an IP address of a router to which the packet is to be sent first from the its own (source) host, when a destination host belongs to a subnetwork which is different from the subnetwork to which the source host belongs. When the destination host and the source host belong to the same subnetwork, the gateway address is not an IP address of a router and, instead, is an IP address of the destination host or an IP address of its own host. The operating system (OS) searches the routing table using the IP address of the destination host as a search key, to obtain the output interface and the gateway address.
In addition, the operating system (OS) contains a data-link-layer address table for each interface, to indicate correspondence between the network-layer addresses and the data-link-layer addresses. For example, ARP (address resolution protocol) tables in UNIX systems having Ethernet interfaces, indicate correspondences between IP addresses and MAC (media access control) addresses. MAC addresses of L2 (layer 2) reachable hosts or gateways can be obtained from their IP addresses, to enable the source host to communicate with these L2 reachable hosts or gateways. When no entry corresponding to an IP address is found, an APR request is sent to all the hosts and gateways in the same subnetwork in accordance with the ARP protocol to obtain the MAC address corresponding to the IP address.
A similar protocol called ATMARP has been proposed for ATM networks. ATM addresses corresponding to IP addresses can be obtained in accordance with the ATMARP protocol. In addition, a procedure for management and control of a plurality of subnetworks over an ATM network, called IPOA (IP over ATM) has been proposed by M. Laubach, "Classical IP and ARP over ATM", Request for comments: 1577, January 1994. According to the IPOA, a plurality of subnetworks, called LIS (Logical IP Subnetwork), are logically defined on an ATM network, and an ATMARP server is provided for each LIS to register and control ATM addresses of terminals in the LIS. Before each terminal sends a packet, the terminal searches its own routing table to determine an output interface, and then searches an ATMARP table which is provided corresponding to the determined output interface to obtain an ATM address or a VC (virtual connection) number of a host or router in the same LIS to which a packet is to be transferred next. When no ATM address corresponding to the IP address is found in the ATMARP table, the terminal inquires of the ATMARP server an ATM address corresponding to the IP address. After the terminal receives a response from the ATMARP server together with the ATM address to the router, each terminal can send the packet to the router as a next hop, and then the packet can be transferred through at least one router to a destination host in a different subnetwork (LIS) based on the IP address of the destination host.
However, the LISs are logically defined on an ATM network in which communication based on a data-link-layer address should be possible without using the router and the network-layer address. Therefore, when it is possible to obtain data-link-layer path information to a destination host in an LIS which is different from the LIS of the source host, it is unnecessary to send the packet through routers which are provided between LISs, and a direct virtual connection (called shortcut path) can be established to the destination host in the different LIS by using the data-link-layer address. In order to obtain the data-link-layer address of a destination host in the different LIS, a protocol called NHRP (Next Hop Resolution Protocol) has been proposed in IETF (Internet Engineering Task Force) by James V. Lucuani et al., "NBMA Next Hop Resolution protocol (NHRP)", Routing over Large Cloud Working Group, INTERNET-DRAFT, &lt;draft-ietf-rolc-nhrp-11.txt&gt;. According to the NHRP, the procedure of the ATMARP is extended to a network containing a plurality of LISs.
According to the NHRP, a server called next hop server (NHS) is provided for each LIS, and each next hop server usually functions as a router between LISs. A terminal (or station) which establishes a virtual connection in accordance with the NHRP protocol is called next hop client (NHC). Each next hop client registers its own IP address and ATM address in the next hop server of the LIS to which the next hop client belongs. When a next hop client which wants to establish a virtual connection to a destination host, the next hop client, which is denoted here as a source next hop client, sends an NHRP request packet to the next hop server in the LIS to which the source next hop client belongs, where the NHRP request packet contains an IP address of the destination host. When the next hop server receives the NHRP request, and determines that the destination host belongs to an LIS which is different from the LIS which the next hop server controls, the next hop server transfers the NHRP request to another NHS (next hop server) in accordance with its own routing table and the IP address of the destination host. Thus, the NHRP request packet is transferred through a hop-by-hop path passing through routers until the NHRP request packet reaches a next hop server to which controls the LIS which the destination host belongs. When a next hop server, which receives the NHRP request, determines that the destination host belongs to the LIS which the next hop server controls, the next hop server searches its own ATM address table for the ATM address corresponding to the IP address of the destination host, and sends an NHRP response containing the ATM address of the destination host, to the source next hop client which has sent the NHRP request, tracing back the path through which the above the NHRP request has been transferred. When the next hop client receives the NHRP response containing the ATM address, the next hop client establishes a shortcut virtual connection (shortcut VC) to the destination host based on the received ATM address. The shortcut virtual connection does not pass a router, and therefore is free from the delays due to packet reconstruction and transfer in the router, to achieve high speed communication. Each next hop client communicates to another host in an LIS which is different from the LIS of the next hop client, through the hop-by-hop path passing through routers, until the ATM address is obtained as above, and then the hop-by-hop path is switched to the above shortcut virtual connection after the ATM address is obtained and the virtual connection established.
According to the conventional packet transmission procedure, the above search of the routing table for the output interface, and the search of the ARP table for the hardware address (data-link-layer address) corresponding to the IP address, are performed for each packet to be sent. When the destination host belongs to the same subnetwork as the source host, the source host searches the ARP table by using the IP address of the destination host as a search key. When the destination host does not belong to the same subnetwork as the source host, the source host searches the ARP table by using the IP address of the gateway router as a search key, where the IP address of the gateway router is obtained from the routing table by searching the routing table by using the IP address of the destination host as a search key. In the case of the ATM interface, the ATM address of a destination host in the same LIS as the source host is obtained from the ATMARP table. When the ATM address is not obtained from the ATMARP table, the source host inquires of the ATMARP server the ATM address corresponding to the IP address of the destination host. After the ATM address is obtained from the ATMARP server, a virtual connection is established to the destination host based on the ATMARP address, and the transmission is performed through the virtual connection. The obtained ATMARP address is written in the ATMARP table, and there is one-to-one correspondence between the virtual connection and an entry of the ATMARP table. When there is an entry, of the ATMARP table, containing an ATM address, and no virtual connection is established corresponding to the entry, a virtual connection corresponding to the entry of the ATMARP table is established before the transmission of a packet.
Since, according to the conventional procedure before the NHRP, all the transmissions to destination hosts in subnetworks other than the subnetwork to which the source host belongs, are performed through routers, the ARP table contains data-link-layer path information for only the router and the hosts in the same subnetwork as the subnetwork the source host belongs to. However, according to the NHRP procedure, ATM addresses of destination hosts in the subnetworks other than the subnetwork to which the source host belongs, are held in a data-link-layer path information table (which may be denoted as an NH cache hereinafter in this specification), and it is possible to transmit a packet through a shortcut virtual connection bypassing the routers, to a destination host in a subnetwork which is different from the subnetwork to which the source host belongs. In the NHRP procedure, it is necessary to give priority to a search for a shortcut virtual connection to a destination host in a different subnetwork, over a search for a virtual connection to a router in the same subnetwork as the source host, where the latter virtual connection to the router is used for transmission through routers. In the NHRP procedure, it is also desirable to reduce a processing amount and a processing time to realize high speed routing processing.
In addition, it is necessary to use the virtual connection to the router in the same subnetwork when there is no shortcut virtual connection to the destination host. However, the tables in the conventional next hop client initially contains no data-link-layer path information (no gateway address) corresponding to IP addresses of destination hosts in the same LIS as the source host. Therefore, the source host cannot start transmission of a packet until the virtual connection to the destination host in the same subnetwork is established.
Further, in the case wherein it is not possible to establish a shortcut path (virtual connection) to a destination host which belongs to a specific subnetwork, and a shortcut path (virtual connection) can be established from a source host to (a representative host of) the specific subnetwork, it is desirable to be able to utilize the shortcut path (virtual connection) to (the representative host of) the specific subnetwork, as a common shortcut path (virtual connection) to all the hosts in the specific subnetwork.
2.2 In addition to the above problems, it is necessary to determine whether or not first and second communication apparatuses, connected to a layer-3 (network-layer) communication network, can communicate with each other through only a layer-2 (data-link-layer) communication path, i.e., without passing through a router which routes a packet based on an destination (IP) address contained in the packet.
In various networks used in companies and campuses, one or more layer-2 communication networks such as FDDI, Ethernet, and ATM, are used. In addition, a plurality of such layer-2 communication networks of the same type or of different types, may be connected to each other through layer 2 connection devices such as bridges, to form a layer-2 communication network within which two arbitrary communication apparatuses connected thereto can communicate with each other by using a layer-2 communication path only. In this specification, all of these layer-2 communication networks including a single layer-2 communication network such as FDDI, Ethernet, and ATM, and any layer-2 communication network which is formed by connecting a plurality of layer-2 communication networks with one or more layer 2 connection devices, are denoted as layer-2-connected communication networks.
It is possible to logically define a layer-3 communication network on at least one of the above layer-2-connected communication network, and such a configuration of a layer-3 communication network logically defined over at least one layer-2-connected communication network is prevailingly used. Such a layer-3 communication network is usually divided into a plurality of subnetworks which are logically defined. As mentioned in the above section 2.1, these subnetworks may correspond to layer-2 communication networks on which the layer-3 communication network is logically formed. Further, the division into a plurality of subnetworks may be performed within a single layer-2-connected communication network for the purposes of security, network management policy, reduction of traffic, and use of existing configurations.
As explained in the above section 2.1, in the above layer-3 communication network, it is desirable for two communication apparatuses belonging to different subnetworks to communicate therebetween by using a layer-2 communication path only (shortcut path). The reachability in the data link layer (which is denoted as layer 2 reachability or L2 reachability in this specification) is a necessary condition for realizing the communication through the shortcut path. Therefore, it is required to investigate and determine the layer 2 reachability for communication between any two communication apparatuses belonging to different subnetworks.
However, conventionally, no way is provided for determining the layer 2 reachability in the layer-3 communication networks configured as above.